package 链表中倒数第k个节点;
//题目描述
//输入一个链表，输出该链表中倒数第k个结点。
public class Solution
{
    public ListNode FindKthToTail(ListNode head,int k)
    {
        //先反转，再数k
        //正数第n-k+1就是倒数第k个节点，需要遍历两次链表，第一次得到链表长度n，第二次找n-k+1
        //双指针法
        //一前一后指针，中间差k-1，同时向尾结点前进，后的到尾结点时，前面的正好到倒数k

        //判断输入
        if (head==null||k<=0)
            return null;
        //定义两个指针
        ListNode node1=head;
        ListNode node2=head;

        //先走k-1步
        for (int i = 0; i < k-1; i++)
        {
            if (node2.next!=null)
                node2=node2.next;
            else
                return null;//当n小于k的情况，先走的指针指向了null
        }
        while (node2.next!=null)
        {
            node1=node1.next;
            node2=node2.next;
        }
        return node1;
    }
}
